package com.leetcode.根据数据结构分类.并查集;

import java.util.HashSet;
import java.util.Set;

/**
 * @author: xiaomi
 * @date: 2021/1/16
 * @description: 803. 打砖块
 * https://leetcode-cn.com/problems/bricks-falling-when-hit/
 * 收藏了，还木有彻底理解。
 */
public class C_803_打砖块 {

    /**
     * 可以把网格看成俯视图，四个顶点才是连接房檐的位置：只要连接房檐的位置才是稳定的。
     * 1.通过并查集进行 union（使用降维将 grid 数组中的元素平铺到 parents 中）
     * ---
     * 是我理解错题意了:
     * 稳定的砖头,指的是[0,0].
     * 怪不得我想通过四个角来进行遍历会显得特别复杂.
     *
     * @param grid
     * @param hits
     * @return
     */
    public int[] hitBricksFail(int[][] grid, int[][] hits) {
        int m = hits.length;
        int n = hits[0].length;
        InnerUnionFind unionFind = new InnerUnionFind(m * n);
        int index = 0;
        Set<Integer> visitedPositionSet = new HashSet<Integer>();
        //1.第一次遍历，通过四个顶格，将砖进行 union
        //感觉这种遍历方式很不方便，似乎不应该是这样的.
        if (grid[0][0] == 1) {

        }
        return new int[0];
    }


    public int[] hitBricks(int[][] grid, int[][] hits) {
        int m = grid.length;
        int n = grid[0].length;
        InnerUnionFind unionFind = new InnerUnionFind(m * n);
        int index = 0;
        //1.由于第一次都是稳定的,所以可以遍历一边直接进行 union
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    unionFind.union(index, 0);
                }
                index++;
            }
        }
        //2.进行 hit
        //怎么 hit ???
        for (int i = 0; i < hits.length; i++) {
            
        }
        return new int[0];
    }

    class InnerUnionFind {
        int[] parents;
        int[] ranks;

        public InnerUnionFind(int capacity) {
            parents = new int[capacity];
            ranks = new int[capacity];
            for (int i = 0; i < capacity; i++) {
                parents[i] = i;
                ranks[i] = 1;
            }
        }

        public int find(int index) {
            while (index != parents[index]) {
                parents[index] = find(parents[index]);
            }
            return parents[index];
        }


        public void union(int index1, int index2) {
            int p1 = find(index1);
            int p2 = find(index2);
            if (p1 == p2) {
                return;
            }
            if (ranks[p1] == ranks[p2]) {
                parents[p1] = parents[p2];
                ranks[p2]++;
            } else if (ranks[p1] < ranks[p2]) {
                parents[p1] = parents[p2];
            } else {
                parents[p2] = parents[p1];
            }
        }
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 0, 0, 0}, {1, 1, 1, 0}};
        int[][] hits = {{1,0}};
        C_803_打砖块 action = new C_803_打砖块();
        action.hitBricks(grid, hits);
    }
}
